__all__ = ["int_sqrt", "int_sqrt_if_perfect", "is_perfect_square",
        "nth_root"]



def int_sqrt(n):
    digits = n.bit_length()
    x = n
    y = 1 << ((digits + 1) >> 1)
    while x > y:
        x = y
        y = (y + n // y) >> 1
    return x


class PerfectSquare:
    q11 = 0x23b
    q63 = 0x402483012450293
    q64 = 0x202021202030213
    q65 = 0x1218a019866014613


def int_sqrt_if_perfect(n):
    if not PerfectSquare.q64 & 1 << (n & 0x3f):
        return None
    m = n % 45045
    if not (PerfectSquare.q63 & 1 << (m % 63)
            and PerfectSquare.q65 & 1 << (m % 65)
            and PerfectSquare.q11 & 1 << (m % 11)):
        return None
    q = int_sqrt(n)
    return q if q ** 2 == n else None


def is_perfect_square(n):
    if n < 0:
        return False
    if not PerfectSquare.q64 & 1 << (n & 0x3f):
        return False
    m = n % 45045
    if not (PerfectSquare.q63 & 1 << (m % 63)
            and PerfectSquare.q65 & 1 << (m % 65)
            and PerfectSquare.q11 & 1 << (m % 11)):
        return False
    q = int_sqrt(n)
    return q ** 2 == n


def nth_root(n, root):
    digits = n.bit_length()
    minus_one = root - 1
    x = n
    y = 1 << ((digits + minus_one) // root)
    while x > y:
        x = y
        y = (y * minus_one + n // y ** minus_one) // root
    return x
